package leetcode.题库.栈;

/**
 * 最长有效括号
 *
 * @author yanzhenming
 * @date 2023/3/27  17:16
 */

/**
 * 描述
 *
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 */

import java.util.Objects;
import java.util.Stack;

/**
 * 思路
 *
 * 用栈存储下标，注意右括号的处理
 */
public class Solution32 {
    public static void main(String[] args) {
        String s1 = new String("");
        String s2 = new String("(()");
        String s3 = new String(")()())");
        System.out.println(longestValidParentheses(s1));
        System.out.println(longestValidParentheses(s2));
        System.out.println(longestValidParentheses(s3));
    }
    public static int longestValidParentheses(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Objects.equals(c, '(')) {
                stack.push(i);
            } else {
                stack.pop(); // 为了使栈顶保存的始终是最右侧的右括号
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}
